package LeetCode热题HOT100;

import 剑指offer.ListNode;
import 力扣题库.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class p95不同的二叉搜索树II {
    public List<TreeNode> generateTrees(int n) {
        if (n==0) {
            return new ArrayList<>();
        }

        return buildTree(1,n);
    }

    private List<TreeNode> buildTree(int start, int end) {
        List<TreeNode> allTrees=new ArrayList<>();
        if (start>end) {
            allTrees.add(null);
            return allTrees;
        }
        if (start==end) {
            allTrees.add(new TreeNode(start));
            return allTrees;
        }

        for (int i = start; i <=end ; i++) {
            List<TreeNode> leftTree=buildTree(start,i-1);//递归左子树
            List<TreeNode> rightTree=buildTree(i+1,end);//递归右子树

            for (TreeNode left:leftTree) {
                for (TreeNode right:rightTree) {
                    TreeNode root=new TreeNode(i);
                    root.left=left;
                    root.right=right;
                    allTrees.add(root);
                }
            }
        }
        return allTrees;
    }

    public static void main(String[] args) {
        List<TreeNode> leftTree=new ArrayList<>();
        leftTree.add(null);
        List<TreeNode> rightTree=new ArrayList<>();
        rightTree.add(new TreeNode(2));
        for (TreeNode left:leftTree) {
            for (TreeNode right:rightTree) {
                System.out.println(right.val);
            }
        }
    }
}
